
use std::cmp::Ordering;

enum BinaryHeapType {
    Min,
    Max,
}

// Define a trait for the comparison function.
trait Compare {
    fn compare(&self, a: &i32, b: &i32) -> Ordering;
}

// Implement the comparison function for min-heap and max-heap.
struct MinHeapCompare;
struct MaxHeapCompare;

impl Compare for MinHeapCompare {
    fn compare(&self, a: &i32, b: &i32) -> Ordering {
        a.cmp(b)
    }
}

impl Compare for MaxHeapCompare {
    fn compare(&self, a: &i32, b: &i32) -> Ordering {
        b.cmp(a)
    }
}

struct BinaryHeap<T: Compare> {
    heap_type: BinaryHeapType,
    values: Vec<i32>,
    num_values: usize,
    compare_func: T,
}

impl<T: Compare> BinaryHeap<T> {
    fn new(heap_type: BinaryHeapType, compare_func: T) -> Self {
        let mut heap = BinaryHeap {
            heap_type,
            values: Vec::with_capacity(16),
            num_values: 0,
            compare_func,
        };
        heap.values.push(i32::MIN); // Reserve space for the 1-based indexing.
        heap
    }

    fn insert(&mut self, value: i32) {
        if self.num_values >= self.values.len() - 1 {
            self.values.extend(vec![i32::MIN; 16]);
        }
        self.num_values += 1;
        self.values.push(value);
        self.percolate_up(self.num_values);
    }

    fn pop(&mut self) -> Option<i32> {
        if self.num_values == 0 {
            None
        } else {
            let result = self.values[1];
            self.values.swap(1, self.num_values);
            self.num_values -= 1;
            self.percolate_down(1);
            Some(result)
        }
    }

    fn num_entries(&self) -> usize {
        self.num_values
    }

    // Helper methods to maintain the heap property.
    fn percolate_up(&mut self, index: usize) {
        let mut child_index = index;
        let mut parent_index = child_index / 2;

        while parent_index > 0 {
            if self.compare_func.compare(&self.values[child_index], &self.values[parent_index]) == Ordering::Less {
                self.values.swap(child_index, parent_index);
                child_index = parent_index;
                parent_index /= 2;
            } else {
                break;
            }
        }
    }

    fn percolate_down(&mut self, index: usize) {
        let mut parent_index = index;
        let mut left_child_index = 2 * parent_index;
        let mut right_child_index = left_child_index + 1;

        while left_child_index <= self.num_values {
            let child_index = if right_child_index <= self.num_values && self.compare_func.compare(&self.values[right_child_index], &self.values[left_child_index]) == Ordering::Less {
                right_child_index
            } else {
                left_child_index
            };

            if self.compare_func.compare(&self.values[parent_index], &self.values[child_index]) == Ordering::Less {
                break;
            }

            self.values.swap(parent_index, child_index);
            parent_index = child_index;
            left_child_index = 2 * parent_index;
            right_child_index = left_child_index + 1;
        }
    }
}

fn main() {
    // Example usage:
    let mut heap = BinaryHeap::new(BinaryHeapType::Min, MinHeapCompare);
    heap.insert(10);
    heap.insert(20);
    heap.insert(5);

    if let Some(value) = heap.pop() {
        println!("Popped: {}", value);
    }

    println!("Number of entries: {}", heap.num_entries());
}

